package leetcode;


/**
 * Created by Ghost on 2014/10/8 0008.
 */
public class Reorder_List {
    public void reorderList(ListNode head) {
        ListNode tmp = head;
        int len = 0;
        while(tmp!=null){
            len++;
            tmp = tmp.next;
        }

        if(len>2){
            int halfLen = len/2+len%2;
            int i=0;
            tmp = head;
            ListNode secondHead = null;
            while(i<halfLen){
                tmp = tmp.next;
                i++;
                if(i==halfLen-1){
                    secondHead = reverse(tmp.next);
                    tmp.next = null;
                }
            }
            mergeList(head, secondHead);
        }
    }
    public void mergeList(ListNode head1, ListNode head2){
        ListNode current = head1;
        while(head2!=null){
            ListNode next2 = head2.next;
            head2.next = current.next;
            current.next = head2;
            current = current.next.next;
            head2 = next2;
        }
    }
    public ListNode reverse(ListNode head){
        if(head!=null){
            ListNode newHead = head;
            ListNode newHeadAft = newHead.next;
            while(newHeadAft!=null){
                ListNode tmp = newHeadAft.next;

                newHeadAft.next = newHead;
                if(newHead==head)
                    newHead.next = null;
                newHead = newHeadAft;
                newHeadAft = tmp;
            }
            return newHead;
        }
        return null;
    }
    public static void main(String[] args){

        int[] a = new int[]{2,3};

        ListNode head  = new ListNode(1);
        ListNode tmp = head;

        for(int i=0;i<a.length;i++){
            tmp.next = new ListNode(a[i]);
            tmp = tmp.next;
        }

        Reorder_List reorder_list = new Reorder_List();
        reorder_list.reorderList(null);

        while(head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
}
